package my.leetcode.solution;

public class P43 {

    public static void main(String[] args) {
        System.out.println(multiply("123","456"));
        System.out.println(multiply("999","999"));
    }

    public static String multiply(String a, String b) {
        if(a.equals("0") || b.equals("0")) {
            return "0";
        }
        int al = a.length(), bl = b.length(), scale = 0;
        StringBuilder sb = new StringBuilder(al * bl);
        for(int i = al - 1;i >= 0;i--) {
            int aInt = toInt(a.charAt(i));
            int j = bl - 1;
            for(;j >= 0;j--) {
                int bInt = toInt(b.charAt(j));
                int r = aInt * bInt + scale;
                setStringBuilder(sb, r % 10, al - i - 1 + bl - j - 1);
                scale = r / 10;
            }
            if(scale != 0) {
                setStringBuilder(sb, scale, al - i - 1 + bl - j - 1);
                scale = 0;
            }
        }

        return sb.reverse().toString();
    }

    public static void setStringBuilder(StringBuilder sb, int r, int bBit) {
        int len = sb.length() - 1;
        if(len < bBit) {
            sb.append(r);
            return;
        }
        int t = toInt(sb.charAt(bBit)) + r, scale = t / 10;
        sb.setCharAt(bBit, (char)((t % 10) + 48));
        while(len >= ++bBit) {
            if(scale == 0) {
                return;
            }
            t = toInt(sb.charAt(bBit)) + scale;
            scale = t / 10;
            sb.setCharAt(bBit, (char)((t % 10) + 48));
        }
        if(scale != 0) {
            sb.append(scale);
        }
    }

    public static int toInt(char c) {
        switch (c) {
            case '0': return 0;
            case '1': return 1;
            case '2': return 2;
            case '3': return 3;
            case '4': return 4;
            case '5': return 5;
            case '6': return 6;
            case '7': return 7;
            case '8': return 8;
            case '9': return 9;
        }
        throw new RuntimeException("不是数字: " + c);
    }

}
